import javax.swing.tree.TreeNode;
import java.sql.SQLOutput;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Main {

    static class TreeNode {
        public char val;
        public BinaryTree.TreeNode left;
        public BinaryTree.TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    }
    public List<List<Integer>> levelOrder2(TreeNode root){
        List<List<Integer>> retList = new ArrayList<>();
        if(root == null){
            return retList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size != 0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                size--;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            retList.add(list);
        }
       return retList;
    }

    //二叉树的层序遍历 II
    class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List< List<Integer>> levelOrder = new LinkedList<List<Integer>>();
            if(root == null){
                return levelOrder;
            }
            Queue<TreeNode>  queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while(! queue.isEmpty()){
                List<Integer> list = new ArrayList<Integer>();
                int size = queue.size();
                for(int i = 0; i < size; i++){
                    TreeNode cur = queue.poll();
                    list.add(cur.val);
                    TreeNode left = cur.left;
                    TreeNode right = cur.right;
                    if(left != null){
                        queue.offer(left);
                    }
                    if(right != null){
                        queue.offer(right);
                    }
                }
                levelOrder.add(0, new ArrayList<>(list));
            }
            return levelOrder;
        }

    }
}


